Existing computer programs known as road-mapping programs provide digital maps, often complete with detailed road networks down to the city-street level. Typically, a user can input a location and the road-mapping program will display an on-screen map of the selected location. Several existing road-mapping products typically include the ability to calculate a best route between two locations. In other words, the user can input two locations, and the road-mapping program will compute the travel directions from the source location to the destination location. The directions are typically based on distance, travel time, etc. Computing the best route between locations may require significant computational time and resources.
Some road-mapping programs compute shortest paths using variants of a well known method attributed to Dijkstra. Note that in this sense “shortest” means “least cost” because each road segment is assigned a cost or weight not necessarily directly related to the road segment's length. By varying the way the cost is calculated for each road, shortest paths can be generated for the quickest, shortest, or preferred routes. Dijkstra's original method, however, is not always efficient in practice, due to the large number of locations and possible paths that are scanned. Instead, many known road-mapping programs use heuristic variations of Dijkstra's method.
More recent developments in road-mapping algorithms utilize a two-stage process comprising a preprocessing phase and a query phase. During the preprocessing phase, the graph or map is subject to an off-line processing such that later real-time queries between any two destinations on the graph can be made more efficiently. Known examples of preprocessing algorithms use geometric information, hierarchical decomposition, and A* search combined with landmark distances.
Customizable route planning (CRP) is a fast technique for computing point-to-point shortest paths in road networks. It relies on three phases: preprocessing, customization, and queries. The preprocessing partitions the graph into multiple levels of loosely connected components of bounded size and creates an overlay graph for each level by replacing each component with a distance-preserving clique connecting its boundary vertices. Clique edge lengths are computed during the customization phase. The query phase uses a bidirectional Dijkstra's algorithm operating on the union of the overlay graphs and the components of the original graph containing the origin and the destination. This search graph is much smaller than the input graph, leading to fast queries. However, CRP has been restricted to simple query scenarios such as point-to-point queries. Extensions to other techniques exist, but are too sensitive to metric changes.